#include <vector>
#include <iostream>

using namespace std;

struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
};

class Solution 
{
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        ListNode * cur1 = list1;
        ListNode * cur2 = list2;
        ListNode * _dummyHead = new ListNode(0);
        ListNode * cur3 = _dummyHead;
        while(cur1 != nullptr || cur2 != nullptr)
        {
            if(cur1 == nullptr && cur2 != nullptr)
            {
                cur3->next = cur2;
                cur2 = cur2->next;
                cur3 = cur3->next;
            }
            else if(cur1 != nullptr && cur2 == nullptr)
            {
                cur3->next = cur1;
                cur1 = cur1->next;
                cur3 = cur3->next;
            }
            else
            {
                if(cur1->val <= cur2->val)
                {
                    cur3->next = cur1;
                    cur1 = cur1->next;
                    cur3 = cur3->next;
                }
                else
                {
                    cur3->next = cur2;
                    cur2 = cur2->next;
                    cur3 = cur3->next;
                }
            }
        }
        ListNode * result = _dummyHead->next;
        delete _dummyHead;
        return result;
    }
};

// 辅助函数：从vector创建链表
ListNode* createList(vector<int>& nums) {
    if (nums.empty()) return nullptr;
    
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    
    for (int i = 1; i < nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    
    return head;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* cur = head;
    cout << "[";
    while (cur != nullptr) {
        cout << cur->val;
        if (cur->next != nullptr) cout << ",";
        cur = cur->next;
    }
    cout << "]";
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    Solution solution;
    
    // 测试案例1：题目示例1 [1,2,4] 和 [1,3,4]
    cout << "测试案例1: ";
    vector<int> nums1_1 = {1, 2, 4};
    vector<int> nums1_2 = {1, 3, 4};
    ListNode* list1_1 = createList(nums1_1);
    ListNode* list1_2 = createList(nums1_2);
    cout << "list1 = ";
    printList(list1_1);
    cout << ", list2 = ";
    printList(list1_2);
    ListNode* result1 = solution.mergeTwoLists(list1_1, list1_2);
    cout << " -> ";
    printList(result1);
    cout << " (期望: [1,1,2,3,4,4])" << endl;
    deleteList(result1);
    
    // 测试案例2：两个空链表
    cout << "测试案例2: ";
    vector<int> nums2_1 = {};
    vector<int> nums2_2 = {};
    ListNode* list2_1 = createList(nums2_1);
    ListNode* list2_2 = createList(nums2_2);
    cout << "list1 = ";
    printList(list2_1);
    cout << ", list2 = ";
    printList(list2_2);
    ListNode* result2 = solution.mergeTwoLists(list2_1, list2_2);
    cout << " -> ";
    printList(result2);
    cout << " (期望: [])" << endl;
    deleteList(result2);
    
    // 测试案例3：一个空链表和一个单节点链表
    cout << "测试案例3: ";
    vector<int> nums3_1 = {};
    vector<int> nums3_2 = {0};
    ListNode* list3_1 = createList(nums3_1);
    ListNode* list3_2 = createList(nums3_2);
    cout << "list1 = ";
    printList(list3_1);
    cout << ", list2 = ";
    printList(list3_2);
    ListNode* result3 = solution.mergeTwoLists(list3_1, list3_2);
    cout << " -> ";
    printList(result3);
    cout << " (期望: [0])" << endl;
    deleteList(result3);
    
    // 测试案例4：一个链表为空，另一个有多个节点
    cout << "测试案例4: ";
    vector<int> nums4_1 = {};
    vector<int> nums4_2 = {1, 2, 3};
    ListNode* list4_1 = createList(nums4_1);
    ListNode* list4_2 = createList(nums4_2);
    cout << "list1 = ";
    printList(list4_1);
    cout << ", list2 = ";
    printList(list4_2);
    ListNode* result4 = solution.mergeTwoLists(list4_1, list4_2);
    cout << " -> ";
    printList(result4);
    cout << " (期望: [1,2,3])" << endl;
    deleteList(result4);
    
    // 测试案例5：两个单节点链表
    cout << "测试案例5: ";
    vector<int> nums5_1 = {1};
    vector<int> nums5_2 = {2};
    ListNode* list5_1 = createList(nums5_1);
    ListNode* list5_2 = createList(nums5_2);
    cout << "list1 = ";
    printList(list5_1);
    cout << ", list2 = ";
    printList(list5_2);
    ListNode* result5 = solution.mergeTwoLists(list5_1, list5_2);
    cout << " -> ";
    printList(result5);
    cout << " (期望: [1,2])" << endl;
    deleteList(result5);
    
    // 测试案例6：两个链表有相同值
    cout << "测试案例6: ";
    vector<int> nums6_1 = {1, 1, 1};
    vector<int> nums6_2 = {1, 1, 1};
    ListNode* list6_1 = createList(nums6_1);
    ListNode* list6_2 = createList(nums6_2);
    cout << "list1 = ";
    printList(list6_1);
    cout << ", list2 = ";
    printList(list6_2);
    ListNode* result6 = solution.mergeTwoLists(list6_1, list6_2);
    cout << " -> ";
    printList(result6);
    cout << " (期望: [1,1,1,1,1,1])" << endl;
    deleteList(result6);
    
    // 测试案例7：一个链表完全小于另一个
    cout << "测试案例7: ";
    vector<int> nums7_1 = {1, 2, 3};
    vector<int> nums7_2 = {4, 5, 6};
    ListNode* list7_1 = createList(nums7_1);
    ListNode* list7_2 = createList(nums7_2);
    cout << "list1 = ";
    printList(list7_1);
    cout << ", list2 = ";
    printList(list7_2);
    ListNode* result7 = solution.mergeTwoLists(list7_1, list7_2);
    cout << " -> ";
    printList(result7);
    cout << " (期望: [1,2,3,4,5,6])" << endl;
    deleteList(result7);
    
    return 0;
}